package m202405.d16;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/16 14:47
 */
public class q70 {


    public int climbStairs(int n) {
        int[] cache = new int[45];
        cache[0] = 1;
        cache[1] = 2;
        return climbStairs(n, cache);
    }

    public int climbStairs(int n, int[] cache) {
        if (cache[n - 1] != 0) {
            return cache[n - 1];
        }
        int res = climbStairs(n - 2, cache) + climbStairs(n - 1, cache);
        cache[n - 1] = res;
        return res;
    }
}
